# -*- coding:utf-8 -*-
# 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
# 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

# 示例 1：
# 输入：nums = [2,0,2,1,1,0]
# 输出：[0,0,1,1,2,2]

# 示例 2：
# 输入：nums = [2,0,1]
# 输出：[0,1,2]

# 示例 3：
# 输入：nums = [0]
# 输出：[0]

# 示例 4：
# 输入：nums = [1]
# 输出：[1]

# 你可以不使用代码库中的排序函数来解决这道题吗？
# 你能想出一个仅使用常数空间的一趟扫描算法吗？

# 注意：对原地的概念理解有偏差
# 原地是指排序过程中整份数据一直存储在nums，只借助了固定的额外空间就完成了排序
# 稳定性是指当nums中存在相同的数值，排完序之后这些数值的顺序应当保持不变
# eg:
#  a a b a b b  =>  a b a b a b
# [2,0,2,1,1,0]    [0,0,1,1,2,2]
# 理解错误为
# eg:
#  a a b a b b  =>  b a b a a b
# [2,0,2,1,1,0]    [0,0,1,1,2,2]
# 也即0a, 1a拍完序之后的顺序要保持不变

# 使用了排序函数2趟扫描解决了问题
# 在上面错误理解的基础上写出的解决方案
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """

        for i in xrange(len(nums)):
            nums[i] = nums[i] * len(nums) + i
        
        nums.sort()
        
        for i in xrange(len(nums)):
            nums[i] = nums[i] // len(nums)


# 解题的思路就是把0往低位放，把2往高位放
# [2,0,2,1,0,1]
#
#  l       r
# [1,0,2,1,0,2]
#  i
#
#  l       r
# [1,0,2,1,0,2]
#    i
#
#    l     r
# [0,1,2,1,0,2]
#    i

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """

        l = 0
        r = len(nums) - 1
        i = 0
        while(i <= r):
            if nums[i] == 0:
                nums[l], nums[i] = nums[i], nums[l]
                i += 1
                l += 1
            elif nums[i] == 2:
                nums[r], nums[i] = nums[i], nums[r]
                r -= 1
            else:
                i += 1
        
        return nums
t = Solution()
print(t.sortColors([2,0,1]))